//
// Created by daiyizheng on 2022/5/5.
//

// n：表示股票价格数组的长度
// i：表示第i天（i的取值范围[0...n-1]）
// k：表示允许的最大交易次数
// dp[i][k]：表示在第i天结束时，最多进行了k次交易的情况下可以获得的最大利润
// 第i天的操作：买入、卖出、休息
// 限制条件：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
// 第i天卖出的话，那么第i天之前必须持有股票
// 第i天买入的话，那么第i天之前必须不持有股票

// 维度定义
// dp[i][k][0]：表示在第i天结束时，最多进行了k次交易后，不持有股票情况下最大利润
// dp[i][k][1]：表示在第i天结束时，最多进行了k次交易后，持有股票情况下最大利润

// 状态转移
// dp[i][k][0]：表示第i天结束的时候经过k次交易且不持股，那么：
// 1.前一天不持股，然后今天休息，最大利润为：dp[i-1][k][0]
// 2.前一天持股，然后今天卖出，最大利润为：dp[i-1[k][1]+prices[i]
// dp[i][k][0]=max(dp[i-1][k][0],dp[i-1[k][1]+prices[i])


// dp[i][k][1]：表示第i天结束的时候经过k次交易且持股，那么：
// 1.前一天持股，然后今天休息，最大利润为：dp[i-1][k][1]
// 2.前一天不持股，然后今天木买入，最大利润为：dp[i-1][k-1][0]-prices[i]
// dp[i][k][1]=max（dp[i-1][k][1]，dp[i-1][k-1][0]-prices[i]）
// k-1的原因：买入操作会使用一次交易